package com.itheima.algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * <h3>钢条切割问题 - 动态规划</h3>
 */
public class CutRodProblem {
    static class Item {
        int index;
        int weight;
        int value;

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public int unitValue() {
            return value / weight;
        }

        @Override
        public String toString() {
            return "Item(" + index + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, 1, 1),
                new Item(2, 2, 5),
                new Item(3, 3, 8),
                new Item(4, 4, 9),
                new Item(5, 5, 10)/*,
                new Item(6, 6, 17),
                new Item(7, 7, 17),
                new Item(8, 8, 20),
                new Item(9, 9, 24),
                new Item(10, 10, 30)*/
        };
        System.out.println(select2(items, 4));
    }

    /*
        if(装不下) {
            dp[i][j] = dp[i-1][j]
        } else { 装得下
            dp[i][j] = max(dp[i-1][j], item.value + dp[i][j-item.weight])
        }
     */
    /*
        二维数组
     */
    static int select(Item[] items, int total) {
        int[][] dp = new int[items.length][total + 1];
        Item item0 = items[0];
        for (int j = 0; j < total + 1; j++) { // 装得下
            if (j >= item0.weight) {
                dp[0][j] = dp[0][j - item0.weight] + item0.value;
            } else {                         // 装不下
                dp[0][j] = 0;
            }
        }
        for (int i = 1; i < dp.length; i++) {
            Item item = items[i];
            for (int j = 0; j < total + 1; j++) {
                int x = dp[i - 1][j]; // 上次的最大价值
                if (j >= item.weight) { // 装得下
                    dp[i][j] = Integer.max(x, dp[i][j - item.weight] + item.value);
                } else {                // 装不下
                    dp[i][j] = x;
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[dp.length - 1][total];
    }

    /*
        一维数组
     */
    static int select2(Item[] items, int total) {
        int[] dp = new int[total + 1];
        Item item0 = items[0];
        for (int j = 0; j < total + 1; j++) { // 装得下
            if (j >= item0.weight) {
                dp[j] = dp[j - item0.weight] + item0.value;
            }
        }
        System.out.println(Arrays.toString(dp));
        for (int i = 1; i < items.length; i++) {
            Item item = items[i];
            for (int j = 0; j < total + 1; j++) {
                int x = dp[j]; // 上次的最大价值
                if (j >= item.weight) { // 装得下
                    dp[j] = Integer.max(x, dp[j - item.weight] + item.value);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[total];
    }
}
